// 广度优先遍历 (BFS) - 使用队列
function bfsGraph(graph, startVet) { //传入一个用邻接表表示的图,以及一个起始顶点
  //顶点遍历序列
  const res = [];
  //队列 - 先进先出(FIFO)
  const queue = [startVet];
  //访问标记,用Set来存储已访问的顶点
  const visited = new Set();
  visited.add(startVet); //将起始顶点加入到访问标记中

  while (queue.length) { //一直循环直到队列为空
    const vet = queue.shift(); // 从队列头部取出顶点
    res.push(vet);
    for (const neighbor of graph.adjList.get(vet)) { //遍历该顶点的所有邻接顶点
      if (visited.has(neighbor)) {
        continue;
      }
      queue.push(neighbor); // 将未访问的邻接顶点加入队列尾部
      visited.add(neighbor);
    }
  }
  return res;
}

// 深度优先遍历 (DFS) - 使用栈
function dfsGraph(graph, startVet) {
  const res = [];
  //栈 - 后进先出(LIFO)
  const stack = [startVet];
  const visited = new Set();
  visited.add(startVet);

  while (stack.length) {
    const vet = stack.pop(); // 从栈顶取出顶点
    res.push(vet);
    // 注意：为了保持遍历顺序的一致性，需要将邻接顶点逆序入栈
    const neighbors = graph.adjList.get(vet);
    for (let i = neighbors.length - 1; i >= 0; i--) {
      const neighbor = neighbors[i];
      if (!visited.has(neighbor)) {
        stack.push(neighbor);
        visited.add(neighbor);
      }
    }
  }
  return res;
}

// 深度优先遍历 (DFS) - 递归实现
function dfsGraphRecursive(graph, startVet, visited = new Set(), res = []) {
  if (visited.has(startVet)) {
    return res;//递归终止条件
  }
  
  visited.add(startVet);
  res.push(startVet);
  
  for (const neighbor of graph.adjList.get(startVet)) { //邻接表
    if (!visited.has(neighbor)) {
      dfsGraphRecursive(graph, neighbor, visited, res);
    }
  }
  
  return res; //如果不是数组类型,则直接返回
}